#include<iostream>
#include<vector>
#include<string>
using namespace std;

class Solution {
public:
    int countSubstrings(string s) {
        int len = s.size();
        vector<vector<bool>> dp(len, vector<bool>(len, false));
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s[i] == s[j]) {
                    if (i == j || i + 1 == j) {
                        dp[i][j] = true;
                    }
                    else {
                        dp[i][j] = dp[i + 1][j - 1];
                    }
                }
            }
        }
        int ans = 0;
        for (int i = 0; i < len; i++) {
            for (int j = i; j < len; j++) {
                ans += dp[i][j];
            }
        }
        return ans;
    }
};

class Solution {
public:
    string longestPalindrome(string s) {
        int len = s.size();
        vector<vector<int>> dp(len, vector<int>(len, 0));
        int left = 0, max_len = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s[i] == s[j]) {
                    if (i == j) dp[i][j] = 1;
                    else if (i + 1 == j) dp[i][j] = 2;
                    else if (dp[i + 1][j - 1]) {
                        dp[i][j] = dp[i + 1][j - 1] + 2;
                    }
                    if (max_len < dp[i][j]) {
                        max_len = dp[i][j];
                        left = i;
                    }
                }
            }
        }
        return s.substr(left, max_len);
    }
};

class Solution {
public:
    bool checkPartitioning(string s) {
        int len = s.size();
        vector<vector<bool>> dp(len, vector<bool>(len, false));
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s[i] == s[j]) {
                    if (i == j) dp[i][j] = true;
                    else if (i + 1 == j) dp[i][j] = true;
                    else dp[i][j] = dp[i + 1][j - 1];
                }
            }
        }
        for (int i = 0; i < len; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                if (dp[0][i] && dp[i + 1][j] && dp[j + 1][len - 1]) {
                    return true;
                }
            }
        }
        return false;
    }
};

class Solution {
public:
    int minCut(string s) {
        int len = s.size();
        vector<vector<bool>> judgeVt(len, vector<bool>(len, 0));
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s[i] == s[j]) {
                    judgeVt[i][j] = i + 1 >= j ? true : judgeVt[i + 1][j - 1];
                }
            }
        }
        vector<int> dp(len, INT_MAX);
        for (int i = 0; i < len; i++) {
            for (int j = 0; j <= i; j++) {
                if (judgeVt[0][i]) dp[i] = 0;
                else if (judgeVt[j][i]) {
                    dp[i] = min(dp[j - 1] + 1, dp[i]);
                }
            }
        }
        return dp[len - 1];
    }
};

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.size();
        vector<vector<int>> dp(len, vector<int>(len, 1));
        int ans = 0;
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s[i] == s[j]) {
                    if (i == j) dp[i][j] = 1;
                    else if (i + 1 == j) dp[i][j] = 2;
                    else dp[i][j] = max(dp[i][j], dp[i + 1][j - 1] + 2);
                }
                else dp[i][j] = max(dp[i][j - 1], dp[i + 1][j]);
                ans = max(ans, dp[i][j]);
            }
        }
        return ans;
    }
};

class Solution {
public:
    int minInsertions(string s) {
        int len = s.size();
        vector<vector<int>> dp(len, vector<int>(len));
        for (int i = len - 1; i >= 0; i--) {
            for (int j = i; j < len; j++) {
                if (s[i] == s[j]) {
                    if (i == j) dp[i][j] = 0;
                    else if (i + 1 == j) dp[i][j] = 0;
                    else dp[i][j] = dp[i + 1][j - 1];
                }
                else dp[i][j] = min(dp[i + 1][j], dp[i][j - 1]) + 1;
            }
        }
        return dp[0][len - 1];
    }
};

